#include <iostream>
#include <vector>
using namespace std;
class Solution {
 public:
  vector<int> path;
  vector<vector<int> > res;
  vector<vector<int> > combinationSum(vector<int>& candidates, int target) {
    // sort(candidates.begin(),candidates.end());  // 排序，剪枝预处理
    backtracking(candidates, 0, target);
    return res;
  }
  void backtracking(vector<int> candidates, int start_index, int target) {
    if (target < 0) return;
    if (target == 0) {
      res.push_back(path);
      return;
    }
    for (int i = start_index; i < candidates.size(); i++) {
      // for (int i = start_index; i < len && target >= candidates[i]; i++) { //
      // 剪枝
      path.push_back(candidates[i]);
      target -= candidates[i];
      backtracking(candidates, i,
                   target);  // 关键点:不用i+1了，表示可以重复读取当前的数
      path.pop_back();
      target += candidates[i];
    }
  }
};